#include <iostream>
#include <vector>
#include <algorithm>
#include <windows.h>
#include <chrono>
#include <functional>
using namespace std;

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        
        vector<vector<int>> ans;
        vector<int> path;

        int n=nums.size();
        function<void(int)> dfs=[&](int i){
            if(i==n)
            {
                ans.push_back(path);
                return ;
            }

            for(int j=0;j<n;j++)
            {
                if(find(path.begin(),path.end(),nums[j])==path.end())
                {
                    path.push_back(nums[j]);
                    dfs(i+1);
                    path.pop_back();
                }
                
            }
        };

        dfs(0);
        return ans;
    }
};



class Solution2 {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>> ans;
        vector<int> path(n);
        vector<bool>on_path(n,false);

       
        function<void(int)> dfs=[&](int i){
            if(i==n)
            {
                ans.push_back(path);
                return ;
            }

            for(int j=0;j<n;j++)
            {
                if(!on_path[j])
                {
                    path[i]=nums[j];
                    on_path[j]=true;
                    dfs(i+1);
                    on_path[j]=false;

                }
            }
        };

        dfs(0);
        return ans;
    }
};

void printResult(const vector<vector<int>>& result) {
    cout << "[";
    for (size_t i = 0; i < result.size(); ++i) {
        cout << "[";
        for (size_t j = 0; j < result[i].size(); ++j) {
            cout << result[i][j];
            if (j < result[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

void runTest(const string& testName, vector<int>& nums, Solution& s1, Solution2& s2) {
    cout << "\n" << testName << "：" << endl;
    cout << "输入：nums = [";
    for (size_t i = 0; i < nums.size(); ++i) {
        cout << nums[i];
        if (i < nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;

    cout << "方法1输出：";
    printResult(s1.permute(nums));
    cout << "方法2输出：";
    printResult(s2.permute(nums));
}

int main() {
    SetConsoleOutputCP(CP_UTF8);
    Solution s1;
    Solution2 s2;
    
    // 测试用例1：标准情况
    vector<int> nums1 = {1, 2, 3};
    runTest("测试用例1 - 标准三个数字", nums1, s1, s2);
    
    // 测试用例2：两个数字
    vector<int> nums2 = {1, 2};
    runTest("测试用例2 - 两个数字", nums2, s1, s2);
    
    // 测试用例3：单个数字
    vector<int> nums3 = {1};
    runTest("测试用例3 - 单个数字", nums3, s1, s2);
    
    // 测试用例4：包含0的情况
    vector<int> nums4 = {0, 1};
    runTest("测试用例4 - 包含0", nums4, s1, s2);
    
    // 测试用例5：较大数字
    vector<int> nums5 = {5, 4, 3};
    runTest("测试用例5 - 较大数字", nums5, s1, s2);

    return 0;
}

